package com.hdu.hot100.trick;

public class lc287 {
    class Solution {
        public int findDuplicate(int[] nums) {
            /**
             * 1,3,4,2,2
             *
             * 0 -> 1
             * 1 -> 3
             * 2 -> 4
             * 3 -> 2
             * 4 -> 2
             *
             *
             * 0 -> 1 -> 3 -> 2 -> 4
             *                |____|
             */

            int slow = 0, fast = 0;
            while (fast != -1)
            {
                slow = nums[slow];
                fast = nums[nums[fast]];
                if (slow == fast)
                {
                    int index = 0;
                    while (index != slow)
                    {
                        index = nums[index];
                        slow = nums[slow];
                    }
                    return index;
                }
            }

            return -1;
        }
    }
}
